//
//Copyright GX. Yuan
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//   http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.

/**
 * @file net.go
 * @brief Leetcode 剑指Offer 第二版
 * @details 剑指 Offer 42. 连续子数组的最大和
 * @author GX. Yuan  any question please send mail to yuanguanxu@qq.com
 * @date 2021-6-28
 * @version V1.0
 * @attention 硬件平台: windows 10 家庭版
 * SDK版本：Go 1.16.5
 * IDE版本：GoLand 2020.2.3
 */
package main
// 使用暴力解法需要的时间复杂是：O(n^2); 即：使用的是两次逻辑循环; 标准的：一次逻辑循环的时间复杂度N,两次N^2

func maxSubArray(nums []int) int {
   max :=nums[0]
    for i:=0;i<len(nums);i++{
        sum:=0
        for j:=i;j<len(nums);j++{
            sum+=nums[j]
            if max<sum{
                max=sum
            }
        }
    }
    return max
}
// 使用动态规划来实现
func maxSubArray(nums []int) int{
    dp :=nums[0]
    max :=nums[0]
    for _,val :=range nums[1:]{ // 对每次增加一个值来 ，判断和子序列的关系，来找到适当的值;
        if dp >0{  // dp >0 的话
            dp += val
        }else{
            dp=val
        }
        if max<dp{
            max = dp
        }
    }
    return max
}
func main() {
	
}
// 动态规划的方式
// 找到动态规划的转移方程:
// 思路围绕着一个目标：找到状态转移方程
// 前面的子序列的最大值与当前值，进行组合找到最大值；如果大于 0 加起来是最大值，如果是小于0 当前值就是最大的值;
